// @algorithm @lc id=32 lang=cpp 
// @title longest-valid-parentheses


// #define print(...)
// @test("(()")=2
// @test(")()())")=4
// @test("")=0
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        vector<int> dp(s.size(), 0);
        for(int i=1; i<(int)s.size(); i++){
            if(s[i] != ')') continue;
            if(s[i-1]=='('){ // s[i-1,i] = "()"
                dp[i] = 2 + (i >= 2 ? dp[i-2] : 0);
            }else if( 1<=i-dp[i-1] && s[i-dp[i-1]-1]=='('){ // s[i-1,i] = "))"
                dp[i] = 2 + dp[i-1] + (2<=i-dp[i-1] ? dp[i-dp[i-1]-2] : 0);
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};